package com.snopy.leetcode.index1_1000.index401_500;

import java.util.*;

/**
 * @author snopy
 * @version 1.0.0
 * @classname Question599
 * @description 两个列表的最小索引总和
 * 假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
 *
 * 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
 *
 * 
 *
 * 示例 1:
 *
 * 输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
 * 输出: ["Shogun"]
 * 解释: 他们唯一共同喜爱的餐厅是“Shogun”。
 * 示例 2:
 *
 * 输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
 * 输出: ["Shogun"]
 * 解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。
 *
 * @email 77912204@qq.com
 * @date 2022/04/07 20:31
 */
public class Question599 {
    public static void main(String[] args) {

        String[] arr1 = new String[]{"Shogun","Tapioca Express","Burger King","KFC"};
        String[] arr2 = new String[]{"KFC","Shogun","Burger King"};
        for (String s : findRestaurant(arr1, arr2)) {
            System.out.println(s);
        }
    }
    public static String[] findRestaurant(String[] list1, String[] list2) {

        Map<String, Integer> index = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            index.put(list1[i], i);
        }

        List<String> ret = new ArrayList<>();
        int k = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if (index.containsKey(list2[i])) {
                int j = index.get(list2[i]);
                if (i + j < k) {
                    ret.clear();
                    ret.add(list2[i]);
                    k = i + j;
                } else if (i + j == k) {
                    ret.add(list2[i]);
                }
            }
        }
        return ret.toArray(new String[0]);
    }
}
